package com.lq.nine;

import javafx.util.Pair;

import java.util.Arrays;
import java.util.List;
import java.util.Map;

/**
 * @author lq
 * @date 2020-09-23 11:21
 */
public class T25reverseKGroup {

    /**
     * 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
     *
     * k 是一个正整数，它的值小于或等于链表的长度。
     *
     * 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
     *
     *  
     *
     * 示例：
     *
     * 给你这个链表：1->2->3->4->5
     *
     * 当 k = 2 时，应当返回: 2->1->4->3->5
     *
     * 当 k = 3 时，应当返回: 3->2->1->4->5
     *
     *  
     *
     * 说明：
     *
     * 你的算法只能使用常数的额外空间。
     * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

     * @param args
     */
    public static void main(String[] args) {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
/*        ListNode r = reverse(n1);
        while (r != null) {
            System.out.println(r.val);
            r = r.next;
        }*/

        ListNode r2 = reverse2(n1);
        while (r2 != null) {
            System.out.println(r2.val);
            r2 = r2.next;
        }

//        ListNode r3 = reverseKGroup(n1, 3);
//        while (r3 != null) {
//            System.out.println(r3.val);
//            r3 = r3.next;
//        }

    }

    //反转链表
    public static ListNode reverse(ListNode node) {
        if (node.next == null) return node;
        ListNode last = reverse(node.next);
        node.next.next = node;
        node.next = null;
        return last;
    }

    //反转列表
    public static ListNode reverse2(ListNode node) {
        ListNode pre = null;
        ListNode curr = node;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        return pre;
    }

    // 分组反转链表
    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode end = dummy;
        while (end.next != null) {
            for (int i = 0; i < k && end != null; i++) {
                end = end.next;
            }
            if (end == null) break;
            ListNode start = pre.next;
            ListNode next = end.next;
            end.next = null;
            pre.next = reverse2(start);
            start.next = next;
            pre = start;
            end = pre;
        }
        return dummy.next;
    }

}
